{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Word Abbreviation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #trie #array #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字典树 #数组 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wordsAbbreviation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词缩写"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串数组 <code>words</code> ，该数组由 <strong>互不相同</strong> 的若干字符串组成，请你找出并返回每个单词的 <strong>最小缩写</strong> 。</p>\n",
    "\n",
    "<p>生成缩写的规则如下<strong>：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>初始缩写由起始字母+省略字母的数量+结尾字母组成。</li>\n",
    "\t<li>若存在冲突，亦即多于一个单词有同样的缩写，则使用更长的前缀代替首字母，直到从单词到缩写的映射唯一。换而言之，最终的缩写必须只能映射到一个单词。</li>\n",
    "\t<li>若缩写并不比原单词更短，则保留原样。</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> words = [\"like\", \"god\", \"internal\", \"me\", \"internet\", \"interval\", \"intension\", \"face\", \"intrusion\"]\n",
    "<strong>输出:</strong> [\"l2e\",\"god\",\"internal\",\"me\",\"i6t\",\"interval\",\"inte4n\",\"f2e\",\"intr4n\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"aa\",\"aaa\"]\n",
    "<strong>输出：</strong>[\"aa\",\"aaa\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 400</code></li>\n",
    "\t<li><code>2 &lt;= words[i].length &lt;= 400</code></li>\n",
    "\t<li><code>words[i]</code> 由小写英文字母组成</li>\n",
    "\t<li><code>words</code> 中的所有字符串 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [word-abbreviation](https://leetcode.cn/problems/word-abbreviation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [word-abbreviation](https://leetcode.cn/problems/word-abbreviation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"like\",\"god\",\"internal\",\"me\",\"internet\",\"interval\",\"intension\",\"face\",\"intrusion\"]', '[\"aa\",\"aaa\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        n = len(words)\n",
    "        prepare = [i for i in range(n)]\n",
    "        m = defaultdict(list)\n",
    "        level = 1\n",
    "        res = [''] * n\n",
    "\n",
    "        def getAbbr(word, level):\n",
    "            if len(word) <= 3:\n",
    "                return word\n",
    "            t = word[:level] + str(len(word) - level - 1) + word[-1]\n",
    "            if len(t) == len(word):\n",
    "                return word\n",
    "            return t\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        while True:\n",
    "            for idx in prepare:\n",
    "                abbr = getAbbr(words[idx], level)\n",
    "                m[abbr].append(idx)\n",
    "            \n",
    "            prepare = []\n",
    "            for k, indices in m.items():\n",
    "                if len(indices) > 1:\n",
    "                    prepare += indices\n",
    "                else:\n",
    "                    res[indices[0]] = k\n",
    "            if len(prepare) == 0:\n",
    "                break\n",
    "            m = defaultdict(list)\n",
    "            level += 1\n",
    "        \n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        def check(str1, str2):\n",
    "            i = j = 0\n",
    "            len1 = len(str1)\n",
    "            len2 = len(str2)\n",
    "            while i < len1 and j < len2:\n",
    "                if str1[i] == str2[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                elif str2[j].isdigit():\n",
    "                    r = j\n",
    "                    while r < len2 and str2[r].isdigit():\n",
    "                        r += 1\n",
    "                    key = int(str2[j:r])\n",
    "                    i += key\n",
    "                    j = r\n",
    "                else:\n",
    "                    return False\n",
    "            return i == len1 and j == len2\n",
    "\n",
    "        ans = []\n",
    "        n = len(words)\n",
    "        for i in range(n):\n",
    "            item = words[i]\n",
    "            leni = len(item)\n",
    "            l = 1\n",
    "            r = leni-2\n",
    "            len1 = len(ans)\n",
    "            while l < r:\n",
    "                newstr = item[:l] + str(r-l+1) + item[r+1:]\n",
    "                flag = True\n",
    "                for j in range(n):\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    item2 = words[j]\n",
    "                    if check(item2, newstr) == True:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    ans.append(newstr)\n",
    "                    break\n",
    "                l += 1\n",
    "            if len(ans) == len1:\n",
    "                ans.append(item)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        d = defaultdict(list)\n",
    "        res = [None for _ in range(len(words))]\n",
    "        def abbreviate(w, k):\n",
    "            n = len(w)\n",
    "            if n < 4:\n",
    "                return w\n",
    "            tmp = w[:k] + str(n - k - 1) + w[-1]\n",
    "            if len(tmp) < n:\n",
    "                return tmp\n",
    "            return w\n",
    "        \n",
    "        # 前缀的长度\n",
    "        pre = 1\n",
    "        for idx, w in enumerate(words):\n",
    "            d[abbreviate(w, pre)].append([w, idx])\n",
    "        pre += 1\n",
    "        # 逐层剥落第一个不相同的前缀下标\n",
    "        while d:\n",
    "            next_d = defaultdict(list)\n",
    "            for k, v in d.items():\n",
    "                if len(v) == 1:\n",
    "                    res[v[0][1]] = k\n",
    "                else:\n",
    "                    for w, idx in v:\n",
    "                        abb = abbreviate(w, pre)\n",
    "                        next_d[abb].append([w, idx])\n",
    "            pre += 1\n",
    "            d = next_d\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        def get_nw(w,pre_l):\n",
    "            l=len(w)-pre_l-1\n",
    "            if l<=1:\n",
    "                return w\n",
    "            return w[0:pre_l]+str(l)+w[-1]\n",
    "        w_map=defaultdict(list)\n",
    "        q=set()\n",
    "        for i,w in enumerate(words):\n",
    "            nw=get_nw(w,1)\n",
    "            w_map[nw].append((w,nw,1,i))\n",
    "            if len(w_map[nw])>1:\n",
    "                q.add(nw)\n",
    "        q=deque(q)\n",
    "        while q:\n",
    "            last=q.popleft()\n",
    "            for w,nw,pre_l,i in w_map[last]:\n",
    "                nw=get_nw(w,pre_l+1)\n",
    "                w_map[nw].append((w,nw,pre_l+1,i))\n",
    "                if len(w_map[nw])>1:\n",
    "                    q.append(nw)\n",
    "            del w_map[last]\n",
    "        for nw,info in w_map.items():\n",
    "            assert len(info)==1\n",
    "            words[info[0][-1]]=nw\n",
    "        return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        def suoxie(word,i=0):\n",
    "            if len(word)-i<=3:return word\n",
    "            return word[:i+1]+str(len(word)-i-2)+word[-1]\n",
    "        n=len(words)\n",
    "        # ans=map(suoxie,words)\n",
    "        ans=[suoxie(i)for i in words]\n",
    "        prefix_len=[0]*n\n",
    "        for i in range(n):\n",
    "            while True:\n",
    "                chongfu=set()\n",
    "                for j in range(i+1,n):\n",
    "                    if ans[i]==ans[j]:chongfu.add(j)\n",
    "                if not chongfu:break\n",
    "                chongfu.add(i)\n",
    "                for k in chongfu:\n",
    "                    prefix_len[k]+=1\n",
    "                    ans[k]=suoxie(words[k],prefix_len[k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        suoxie_dict = {}\n",
    "        for word in words:\n",
    "            if len(word) <= 3:\n",
    "                suoxie_dict[word] = word\n",
    "            else:\n",
    "                for a in range(1, len(word) - 1):\n",
    "                    if a == len(word) - 2:\n",
    "                        suoxie = word\n",
    "                    else:\n",
    "                        suoxie = word[:a] + str(len(word) - a - 1) + word[-1]\n",
    "                    if suoxie in suoxie_dict.keys():\n",
    "                        if suoxie_dict[suoxie] != '0':\n",
    "                            last_word = suoxie_dict[suoxie]\n",
    "                            if a == len(word) - 3:\n",
    "                                suoxie_dict[last_word] = last_word\n",
    "\n",
    "                            else:\n",
    "                                last_suoxie = last_word[:a+1] + str(len(word) - a - 2) + word[-1]\n",
    "                                suoxie_dict[last_suoxie] = last_word\n",
    "                            suoxie_dict[suoxie] = '0'\n",
    "                        else:\n",
    "                            continue\n",
    "                    else:\n",
    "                        suoxie_dict[suoxie] = word\n",
    "                        break\n",
    "        ans = {}\n",
    "        for key in suoxie_dict.keys():\n",
    "            if suoxie_dict[key]!='0':\n",
    "                ans[suoxie_dict[key]] = key\n",
    "        return [ans[word] for word in words]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, lst: List[str]) -> List[str]:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        def abbr(word, target_len=3):\n",
    "            # 用来生成缩略词的函数，target_len是最终的缩略词长度\n",
    "            if len(word) <= target_len:\n",
    "                return word\n",
    "            else:\n",
    "                return word[0:target_len - 2] + str(len(word) - target_len + 1) + word[-1]\n",
    "\n",
    "        def recur(words, target_len=3):\n",
    "            # 返回满足条件的单词-缩略词字典映射，以及不唯一的单词作为remaining，后续需要继续处理\n",
    "            abbr_dict = defaultdict(list)\n",
    "            for word in words:\n",
    "                abbr_dict[abbr(word, target_len)].append(word)\n",
    "\n",
    "            res = {}\n",
    "            remaining = []\n",
    "            for key, values in abbr_dict.items():\n",
    "                if len(abbr_dict[key]) == 1: # 结果唯一，记录单词形如: {'like': 'l2e'}\n",
    "                    res[values[0]] = key\n",
    "                else:\n",
    "                    remaining.extend(values) # 缩略词不唯一的单词将被收录到remaining中\n",
    "            return res, remaining\n",
    "\n",
    "        words = lst\n",
    "        res = {}\n",
    "        target_len = 3\n",
    "        while words:\n",
    "            tmp_res, words = recur(words, target_len)  # 缩略词不唯一的单词，重新做为word，进行下一次循环\n",
    "            res.update(tmp_res) # 更新结果字典\n",
    "            target_len += 1\n",
    "\n",
    "        res_list = [res[word] for word in lst] # 按顺序输出缩略词\n",
    "\n",
    "        return res_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param words:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ans_m = {}\n",
    "        def get_short(w, prev):\n",
    "            changed = w[:1+prev] + str(len(w[prev+1:-1])) + w[-1]\n",
    "            if len(changed) < len(w):\n",
    "                ans_m[w] = changed\n",
    "                return changed\n",
    "            ans_m[w] = w\n",
    "            return w\n",
    "\n",
    "        def get_ans(ll, prev):\n",
    "            m1 = defaultdict(list)\n",
    "            for i in ll:\n",
    "                shorted = get_short(i, prev)\n",
    "                m1[shorted].append(i)\n",
    "            ret = []\n",
    "            for i in m1:\n",
    "                if len(m1[i]) == 1:\n",
    "                    ret.append(i)\n",
    "                else:\n",
    "                    x1 = get_ans(m1[i], prev+1)\n",
    "                    for x in x1:\n",
    "                        ret.append(x)\n",
    "            return ret\n",
    "\n",
    "        get_ans(words, 0)\n",
    "        ret2 = []\n",
    "        for i in words:\n",
    "            ret2.append(ans_m[i])\n",
    "        return ret2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param words:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ans_m = {}\n",
    "        def get_short(w, prev):\n",
    "            changed = w[:1+prev] + str(len(w[prev+1:-1])) + w[-1]\n",
    "            if len(changed) < len(w):\n",
    "                ans_m[w] = changed\n",
    "                return changed\n",
    "            ans_m[w] = w\n",
    "            return w\n",
    "\n",
    "        def get_ans(ll, prev):\n",
    "            m1 = defaultdict(list)\n",
    "            for i in ll:\n",
    "                shorted = get_short(i, prev)\n",
    "                m1[shorted].append(i)\n",
    "            ret = []\n",
    "            for i in m1:\n",
    "                if len(m1[i]) == 1:\n",
    "                    ret.append(i)\n",
    "                else:\n",
    "                    x1 = get_ans(m1[i], prev+1)\n",
    "                    for x in x1:\n",
    "                        ret.append(x)\n",
    "            return ret\n",
    "\n",
    "        ret = get_ans(words, 0)\n",
    "        ret2 = []\n",
    "        for i in words:\n",
    "            ret2.append(ans_m[i])\n",
    "        return ret2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        def generate_abb(word, prefix_len):\n",
    "            mid_len = len(word) - prefix_len - 1\n",
    "            abb = word[:prefix_len] + (str(mid_len) if mid_len > 0 else '') + word[-1]\n",
    "            return abb if len(abb) < len(word) else word\n",
    "\n",
    "        def recursion(remain_words, prefix_len):\n",
    "            abb_words = collections.defaultdict(list)\n",
    "            for word in remain_words:\n",
    "                abb_words[generate_abb(word, prefix_len)].append(word)\n",
    "            new_remain_words = []\n",
    "            for k, v in abb_words.items():  # k: abb word, v: list of words with same abb\n",
    "                if len(v) == 1:\n",
    "                    res[v[0]] = k\n",
    "                else:\n",
    "                    new_remain_words.extend(v)\n",
    "            if new_remain_words:\n",
    "                recursion(new_remain_words, prefix_len + 1)\n",
    "\n",
    "        res = {}\n",
    "        recursion(words, 1)\n",
    "        return [res[word] for word in words]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        def dfs(i, cur):\n",
    "            if i == key[1] - 3:\n",
    "                for j in cur:   ans[j] = words[j]\n",
    "                return\n",
    "            visit = {}\n",
    "            for j in cur:\n",
    "                if not visit.get(words[j][i], []):  visit[words[j][i]] = []\n",
    "                visit[words[j][i]].append(j)\n",
    "\n",
    "            for j in visit:\n",
    "                if len(visit[j]) == 1:  \n",
    "                    ans[visit[j][0]] =  \"{}{}{}\".format(words[visit[j][0]][:i+1], \\\n",
    "                    len(words[visit[j][0]]) - 2 - i, words[visit[j][0]][-1])\n",
    "                else:   dfs(i+1, visit[j])              \n",
    "        \n",
    "        wordDict = collections.defaultdict(list)\n",
    "        ans = [\"\"] * len(words)\n",
    "        for i in range(len(words)):\n",
    "            if len(words[i]) <= 3:  ans[i] = words[i]\n",
    "            else:   wordDict[(words[i][-1], len(words[i]))].append(i)\n",
    "        \n",
    "        for key in wordDict:\n",
    "            if len(wordDict[key]) == 1:\n",
    "                i = wordDict[key][0]\n",
    "                ans[i] = \"{}{}{}\".format(words[i][0], len(words[i]) - 2, words[i][-1])\n",
    "            else:\n",
    "                dfs(0, wordDict[key])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        n = len(words)\n",
    "        # 长度和末尾字符分字典树\n",
    "        gp = defaultdict(dict)\n",
    "        for word in words:\n",
    "            pos = gp[(len(word),word[-1])]\n",
    "            for w in word:\n",
    "                if w not in pos:\n",
    "                    pos[w] = {}\n",
    "                    pos[w]['cnt'] = 1\n",
    "                else:\n",
    "                    pos[w]['cnt'] += 1\n",
    "                pos = pos[w]\n",
    "            # pos['word'] = word\n",
    "        \n",
    "        res = []\n",
    "        for word in words:\n",
    "            pos = gp[(len(word),word[-1])]\n",
    "            \n",
    "            s = ''\n",
    "            for w in word:\n",
    "                s += w\n",
    "                pos = pos[w]\n",
    "                if pos['cnt'] == 1:\n",
    "                    break\n",
    "            d = len(word) - len(s) - 1\n",
    "            s += str(d) + word[-1]\n",
    "            \n",
    "            if len(s) < len(word):\n",
    "                res.append(s)\n",
    "            else:\n",
    "                res.append(word)\n",
    "        return res\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    __slots__ = ['children', 'cnt']\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.cnt = 0\n",
    "\n",
    "    def insert(self, w: str):\n",
    "        node = self\n",
    "        for c in w:\n",
    "            idx = ord(c) - ord('a')\n",
    "            if not node.children[idx]:\n",
    "                node.children[idx] = Trie()\n",
    "            node = node.children[idx]\n",
    "            node.cnt += 1\n",
    "\n",
    "    def search(self, w: str) -> int:\n",
    "        node = self\n",
    "        cnt = 0\n",
    "        for c in w:\n",
    "            cnt += 1\n",
    "            idx = ord(c) - ord('a')\n",
    "            node = node.children[idx]\n",
    "            if node.cnt == 1:\n",
    "                return cnt\n",
    "        return len(w)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        tries = {}\n",
    "        for w in words:\n",
    "            m = len(w)\n",
    "            if (m, w[-1]) not in tries:\n",
    "                tries[(m, w[-1])] = Trie()\n",
    "            tries[(m, w[-1])].insert(w)\n",
    "        ans = []\n",
    "        for w in words:\n",
    "            cnt = tries[(len(w), w[-1])].search(w)\n",
    "            ans.append(w if cnt + 2 >= len(w) else w[:cnt] + str(len(w) - cnt - 1) + w[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.child = {}\n",
    "        self.cnt = 0\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        root = self\n",
    "        for c in word:\n",
    "            if c not in root.child:\n",
    "                root.child[c] = Trie()\n",
    "            root = root.child[c]\n",
    "            root.cnt += 1\n",
    "\n",
    "    def unique(self, word: str) -> bool:\n",
    "        ans = 0\n",
    "        root = self\n",
    "        for c in word:\n",
    "            ans += 1\n",
    "            root = root.child[c]\n",
    "            if root.cnt == 1:\n",
    "                break\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        d = defaultdict(Trie)\n",
    "        for x in words:\n",
    "            if (len(x),x[-1]) not in d:\n",
    "                d[(len(x),x[-1])] = Trie()\n",
    "            d[(len(x),x[-1])].insert(x)\n",
    "        \n",
    "        ans = []\n",
    "        for x in words:\n",
    "            need = d[(len(x),x[-1])].unique(x)\n",
    "            ans.append(x[:need] + str(len(x) - need - 1) + x[-1] if need < len(x) - 2 else x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.cnt = 0\n",
    "\n",
    "    def insert(self, w: str):\n",
    "        node = self\n",
    "        for c in w:\n",
    "            idx = ord(c) - ord('a')\n",
    "            if not node.children[idx]:\n",
    "                node.children[idx] = Trie()\n",
    "            node = node.children[idx]\n",
    "            node.cnt += 1\n",
    "\n",
    "    def search(self, w: str) -> int:\n",
    "        node = self\n",
    "        cnt = 0\n",
    "        for c in w:\n",
    "            cnt += 1\n",
    "            idx = ord(c) - ord('a')\n",
    "            node = node.children[idx]\n",
    "            if node.cnt == 1:\n",
    "                return cnt\n",
    "        return len(w)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        tries = {}\n",
    "        for w in words:\n",
    "            m = len(w)\n",
    "            if (m, w[-1]) not in tries:\n",
    "                tries[(m, w[-1])] = Trie()\n",
    "            tries[(m, w[-1])].insert(w)\n",
    "        ans = []\n",
    "        for w in words:\n",
    "            cnt = tries[(len(w), w[-1])].search(w)\n",
    "            ans.append(w if cnt + 2 >= len(w) else w[:cnt] + str(len(w) - cnt - 1) + w[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNone:\n",
    "    def __init__(self, val = None):\n",
    "        self.val = val\n",
    "        self.child = [None for _ in range(26)]\n",
    "        self.ways = 0\n",
    "\n",
    "    def find_way_num(self):\n",
    "        def dfs(node):\n",
    "            flag = 1\n",
    "            for child in node.child:\n",
    "                if child:\n",
    "                    dfs(child)\n",
    "                    flag = 0\n",
    "                    node.ways += child.ways\n",
    "\n",
    "            if flag:\n",
    "                node.ways = 1\n",
    "            \n",
    "        dfs(self)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        \n",
    "        def num(a):\n",
    "            return ord(a) - ord('a')\n",
    "\n",
    "        c = {}\n",
    "        n = len(words)\n",
    "\n",
    "        for i in range(n):\n",
    "            word = words[i]\n",
    "            t = word[0] + str(len(word) - 2) + word[-1]\n",
    "            if len(word) <= 3:\n",
    "                pass\n",
    "            else:\n",
    "                if t not in c:\n",
    "                    c[t] = TreeNone(word[0])\n",
    "                    nownode = c[t]\n",
    "                    for i in range(1, len(word)):\n",
    "                        nownode.child[num(word[i])] = TreeNone(word[i])\n",
    "                        nownode = nownode.child[num(word[i])]\n",
    "                    continue\n",
    "                \n",
    "                nownode = c[t]\n",
    "                for i in range(1, len(word)):\n",
    "                    if not nownode.child[num(word[i])]:\n",
    "                        nownode.child[num(word[i])] = TreeNone(word[i])\n",
    "                    nownode = nownode.child[num(word[i])]\n",
    "\n",
    "        for node in c.values():\n",
    "            node.find_way_num()\n",
    "            # def dfs(node):\n",
    "            #     if not node:\n",
    "            #         return\n",
    "            #     print(node.val, node.ways)\n",
    "            #     for child in node.child:\n",
    "            #         dfs(child)\n",
    "            # dfs(node)\n",
    "            # print()\n",
    "            \n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            if len(word) <= 3:\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                t = word[0] + str(len(word) - 2) + word[-1]\n",
    "                nownode = c[t]\n",
    "                i = 0\n",
    "                while nownode.ways != 1:\n",
    "                    i += 1\n",
    "                    nownode = nownode.child[num(word[i])]\n",
    "                    \n",
    "                i += 1\n",
    "                temp_word = word[:i] + str(len(word) - 1 - i) + word[-1]\n",
    "                if len(temp_word) < len(word):\n",
    "                    ans.append(temp_word)\n",
    "                else:\n",
    "                    ans.append(word)\n",
    "        return ans\n",
    "                \n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNone:\n",
    "    def __init__(self, val = None):\n",
    "        self.val = val\n",
    "        self.child = [None for _ in range(26)]\n",
    "        self.ways = 0\n",
    "\n",
    "    def find_way_num(self):\n",
    "        def dfs(node):\n",
    "            flag = 1\n",
    "            for child in node.child:\n",
    "                if child:\n",
    "                    dfs(child)\n",
    "                    flag = 0\n",
    "                    node.ways += child.ways\n",
    "\n",
    "            if flag:\n",
    "                node.ways = 1\n",
    "            \n",
    "        dfs(self)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordsAbbreviation(self, words: List[str]) -> List[str]:\n",
    "        \n",
    "        def num(a):\n",
    "            return ord(a) - ord('a')\n",
    "\n",
    "        c = {}\n",
    "        n = len(words)\n",
    "\n",
    "        for i in range(n):\n",
    "            word = words[i]\n",
    "            t = word[0] + str(len(word) - 2) + word[-1]\n",
    "            if len(word) <= 3:\n",
    "                pass\n",
    "            else:\n",
    "                if t not in c:\n",
    "                    c[t] = TreeNone(word[0])\n",
    "                    nownode = c[t]\n",
    "                    for i in range(1, len(word)):\n",
    "                        nownode.child[num(word[i])] = TreeNone(word[i])\n",
    "                        nownode = nownode.child[num(word[i])]\n",
    "                    continue\n",
    "                \n",
    "                nownode = c[t]\n",
    "                for i in range(1, len(word)):\n",
    "                    if not nownode.child[num(word[i])]:\n",
    "                        nownode.child[num(word[i])] = TreeNone(word[i])\n",
    "                    nownode = nownode.child[num(word[i])]\n",
    "\n",
    "        for node in c.values():\n",
    "            node.find_way_num()\n",
    "            # def dfs(node):\n",
    "            #     if not node:\n",
    "            #         return\n",
    "            #     print(node.val, node.ways)\n",
    "            #     for child in node.child:\n",
    "            #         dfs(child)\n",
    "            # dfs(node)\n",
    "            # print()\n",
    "            \n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            if len(word) <= 3:\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                t = word[0] + str(len(word) - 2) + word[-1]\n",
    "                nownode = c[t]\n",
    "                i = 0\n",
    "                while nownode.ways != 1:\n",
    "                    i += 1\n",
    "                    nownode = nownode.child[num(word[i])]\n",
    "                    \n",
    "                i += 1\n",
    "                temp_word = word[:i] + str(len(word) - 1 - i) + word[-1]\n",
    "                if len(temp_word) < len(word):\n",
    "                    ans.append(temp_word)\n",
    "                else:\n",
    "                    ans.append(word)\n",
    "        return ans\n",
    "                \n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
